import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Intcmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1,Integer o2){
        return o2.compareTo(o1);
    }


}
public class Heap {
    public int[] elem;
    public int useSize;
    public Heap() {
        this.elem = new int[10];
    }
    public void init(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            useSize++;
        }
    }
    public void swap(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    //初始化后调整为堆(大根堆) 时间复杂度：O(N)
    public void creatHeap(){
        //从下向上调整，时间复杂度低
        for (int parent = (useSize - 1 - 1) / 2;parent >= 0;parent--) {
            //找到根节点向下调整
            siftdown(parent,useSize);
            //siftup(child);
        }
    }

    public void offer(int val){
        if (isFull()){
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[useSize] = val;
        useSize++;
        siftup(useSize - 1);
    }

    public int poll(){
        if (isEmpty()){
            return -1;
        }
        int old = elem[0];
        swap(0,useSize - 1);
        useSize--;
        siftdown(0,useSize);
        return old;
    }
    public void siftdown(int parent,int end){
        int child = 2 * parent + 1;
        while(child < end) {
            //左右比较选出最大值
            if(child + 1 < end && elem[child] < elem[child+1]){
                child++;
            }
            if (elem[parent] < elem[child]) {
                //这里传下标进去交换
                swap(parent,child);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    public void siftup(int child){
         int parent = (child - 1) / 2;
         while(parent >= 0){
             if (elem[parent] < elem[child]){
                 swap(parent,child);
                 child = parent;
                 parent = (child - 1) / 2;
             }else {
                 break;
             }
         }
    }
    public int[] smallK(int[] arr,int k) {
        //创建大根堆
        PriorityQueue<Integer> maxheap = new PriorityQueue<>(new Intcmp());
        //将k个元素放进堆里
        for (int i = 0; i < k; i++) {
            maxheap.offer(arr[i]);
        }
        //比较后续元素
        for (int i = k; i < arr.length; i++) {
            int tmp = maxheap.peek();
            if (tmp > arr[i]) {
                maxheap.poll();
                maxheap.offer(arr[i]);
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = maxheap.poll();
        }
        return ans;
    }
    public void heapSort() {
        //前提先是一个大根堆
        int endIndex = useSize -1;
        while (endIndex > 0) {
            swap(0,endIndex);
            siftdown(0,endIndex);
            endIndex--;
        }
    }
    public int size(){
        return useSize - 1;
    }
    public boolean isEmpty(){
        return useSize == 0;
    }

    public boolean isFull(){
        return useSize == elem.length;
    }
    public int peekHeap(){
        return elem[0];
    }
}
